﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using SmartMathLibrary.Statistics.RandomNumberGenerator;

namespace SmartMathLibrary
{
    /// <summary>
    /// The static primenumber class provides methods to check if a number is prime or not.
    /// </summary>
    [Serializable]
    public static class Primenumbers
    {
        /// <summary>
        /// Determines whether a number is a primenumber. The number will be checked by 
        /// the theorem Fermat.
        /// </summary>
        /// <param name="primeNumber">The primenumber to check.</param>
        /// <returns>
        /// 	<c>true</c> if the number is prime otherwise, <c>false</c>.
        /// </returns>
        public static bool IsPrimeFermat(uint primeNumber)
        {
            return Primenumbers.IsPrimeFermat(primeNumber, 2);
        }

        /// <summary>
        /// Determines whether a number is a primenumber. The number will be checked by 
        /// the theorem Fermat.
        /// </summary>
        /// <param name="primeNumber">The primenumber to check.</param>
        /// <param name="checkBase">The base of the number for checking if its prime.</param>
        /// <returns>
        /// 	<c>true</c> if the number is prime otherwise, <c>false</c>.
        /// </returns>
        public static bool IsPrimeFermat(uint primeNumber, int checkBase)
        {
            if (ExtendedMath.IsOdd(primeNumber))
            {
                return Math.Pow(checkBase, primeNumber - 1) % primeNumber == 1;
            }

            return false;
        }

        /// <summary>
        /// Determines whether a number is a primenumber. The number will be checked by 
        /// the theorem Euler.
        /// </summary>
        /// <param name="primeNumber">The primenumber to check.</param>
        /// <returns>
        /// 	<c>true</c> if the number is prime otherwise, <c>false</c>.
        /// </returns>
        public static bool IsPrimeEuler(uint primeNumber)
        {
            return Primenumbers.IsPrimeEuler(primeNumber, 2);
        }

        /// <summary>
        /// Determines whether a number is a primenumber. The number will be checked by 
        /// the theorem Euler.
        /// </summary>
        /// <param name="primeNumber">The primenumber to check.</param>
        /// <param name="checkBase">The base of the number for checking if its prime.</param>
        /// <returns>
        /// 	<c>true</c> if the number is prime otherwise, <c>false</c>.
        /// </returns>
        public static bool IsPrimeEuler(uint primeNumber, int checkBase)
        {
            if (ExtendedMath.IsOdd(primeNumber))
            {
                return Math.Pow(checkBase, (primeNumber - 1) / 2.0) % primeNumber == 1;
            }

            return false;
        }

        /// <summary>
        /// Determines whether a number is a primenumber. The number will be checked by 
        /// the theorem Wilson.
        /// </summary>
        /// <param name="primeNumber">The primenumber to check.</param>
        /// <returns>
        /// 	<c>true</c> if the number is prime otherwise, <c>false</c>.
        /// </returns>
        public static bool IsPrimeWilson(uint primeNumber)
        {
            return (Factorials.Factorial(primeNumber - 1) + 1) % primeNumber == 0;
        }

        /// <summary>
        /// Determines whether a number is a primenumber. The number will be checked by 
        /// the Rabbin-Miller Test.
        /// </summary>
        /// <param name="primeNumber">The primenumber to check.</param>
        /// <returns>
        /// 	<c>true</c> if the number is prime otherwise, <c>false</c>.
        /// </returns>
        public static bool IsPrimeRabbinMiller(uint primeNumber)
        {
            if (primeNumber == 3u)
            {
                throw new ArgumentException("primeNumber == 3u", "primeNumber");
            }

            ExtendedRandom random = new ExtendedRandom();

            return Witness(random.Next(2, primeNumber - 2), primeNumber - 1, primeNumber) == 1;
        }

        /// <summary>
        /// This method implements the Rabin-Miller Primetest.
        /// </summary>
        /// <param name="a">A random number for the test.</param>
        /// <param name="i">A random number for the test.</param>
        /// <param name="n">The primenumber to check.</param>
        /// <returns>The method returns a 0 if it is a primenumber otherwise its not a primenumber.</returns>
        private static uint Witness(uint a, uint i, uint n)
        {
            uint x, y;

            if (i == 0)
            {
                return 1;
            }

            x = Witness(a, i / 2, n);

            if (x == 0)
            {
                return 0;
            }

            y = (x * x) % n;

            if (y == 1 && x != 1 && x != n - 1)
            {
                return 0;
            }

            if (i % 2 != 0)
            {
                y = (a * y) % n;
            }

            return y;
        }

        /// <summary>
        /// Generates a list of primenumbers.
        /// </summary>
        /// <param name="seek">The border to which the list should be seek.</param>
        /// <returns>A list of primenumbers.</returns>
        public static IntNumberCollection GeneratePrimeNumbers(int seek)
        {
            if (seek < 0)
            {
                throw new ArgumentException("seek < 0", "seek");
            }

            bool[] primes = new bool[seek];
            IntNumberCollection primenumbers = new IntNumberCollection();

            for (int n = 2; n < primes.Length; n++)
            {
                primes[n] = true;
            }

            for (int n = 2; n < Math.Sqrt(primes.Length); n++)
            {
                if (primes[n])
                {
                    for (int i = 2 * n; i < primes.Length; i += n)
                    {
                        primes[i] = false;
                    }
                }
            }

            for (int n = 2; n < primes.Length; n++)
            {
                if (primes[n])
                {
                    primenumbers.Add(n);
                }
            }

            return primenumbers;
        }

        /// <summary>
        /// Gets the next primenumber, relative to the specified number. The numbers
        /// will be checked by the RabbinMiller Test.
        /// </summary>
        /// <param name="value">The specified number.</param>
        /// <returns>The found primenumber.</returns>
        public static uint NextPrimeNumber(uint value)
        {
            if (ExtendedMath.IsEven(value))
            {
                value++;
            }
            else
            {
                value += 2;
            }

            while (!Primenumbers.IsPrimeRabbinMiller(value))
            {
                value += 2;
            }

            return value;
        }

        /// <summary>
        /// Gets the previous primenumber, relative to the specified number. The numbers
        /// will be checked by the RabbinMiller Test.
        /// </summary>
        /// <param name="value">The specified number.</param>
        /// <returns>The found primenumber.</returns>
        public static uint PreviousPrimeNumber(uint value)
        {
            if (value <= 1)
            {
                return 1;
            }

            if (ExtendedMath.IsEven(value))
            {
                value--;
            }
            else
            {
                value -= 2;
            }

            while ((!Primenumbers.IsPrimeRabbinMiller(value)) && (value > 1))
            {
                value -= 2;
            }

            return value;
        }
    }
}